1. Field of the Invention
This invention relates to the field of data communications, and in particular to the field of secure data communications via systems that employ the Data Encryption System (DES) encryption algorithm.
2. Description of Related Art
The Data Encryption System (DES) encryption algorithm is one of the most widely used symmetric key ciphers in the world. The DES encryption algorithm and associated standards were developed in an era when 8-bit devices and architectures were prevalent. The DES standard includes a permutation of a 64-bit internal data structure to a sequence of 8-bit data elements, to facilitate the use of an 8-bit bus structure. FIGS. 1 and 2 illustrate the permutation of the DES 64-bit structure to and from an 8-bit structure.
In FIG. 1, a 64-bit shift register 100 simultaneously transfers eight selected bits 108, 116, 124, 132, 140, 148, 156, and 164 to an 8-bit output register 190. The output register 190 is conventionally associated with an 8-bit data bus (not shown). Another device on the data bus, for example, the transmitter 520 in FIG. 5, can thereafter access these eight bits via the data bus, for subsequent actions, such as transmission to a receiver 570 in FIG. 5. After the eight bits are xe2x80x9cunloadedxe2x80x9d 171 onto the data bus, the 64-bit shift register 100 shifts each of its bits down, in the direction of the shift arrow 172. In so doing, the contents of the register at the eight selected bit locations 108, 116, 124, 132, 140, 148, 156, and 164 receive the value of the previously immediately adjacent bit locations 107, 115, 123, 131, 139, 147, 155, and 163. These new values at the eight selected bit locations are transferred to the 8-bit output register 190, for subsequent access by the other device or devices on the data bus. This unload 171 and shift 172 process is repeated until the 64-bit data in shift register 100 is communicated as eight 8-bit data elements via the register 190. That is, after seven shifts, the value from the first bit location 101 of shift register 100 will be located in the selected bit location 108, and transferred to the output register 190. As illustrated in FIG. 1, the contents of the eight selected bit locations 108, 116, 124, 132, 140, 148, 156, and 164 are transferred to the output register 190 in a permuted form. The fortieth register 140 of shift register 100 is associated with the first bit location 191 of shift register 190; the eighth register 108 of shift register 100 is associated with the second bit location 192 of the shift register 190; and so on.
In FIG. 2, a 64-bit shift register 200 simultaneously receives eight selected bits 201, 209, 217, 225, 233, 241, 249, and 257 from an 8-bit input register 290. The input register 290 is conventionally associated with an 8-bit data bus (not shown), and corresponds to the output register 190. The registers 190, 290 are presented herein for ease of understanding; in many embodiments, the 8-bit data is presented directly to the 8-bit data bus from the shift registers 100, 200, without the use of the intervening registers 190, 290. That is, for example, the transmitter 520 in FIG. 5 will receive the aforementioned selected bits from a register 100 in the encrypter 510 via the 8-bit register 190, or an 8-bit data bus, and transmit these bit values to the receiver 570; the receiver 570 will place the received eight bits from the transmitter 520 into the 8-bit register 290, or onto an 8-bit data bus, for subsequent access by a decrypter 560 that contains the 64 bit shift register 200. After receiving the data from the 8-bit register 290, the 64-bit shift register 200 shifts each of its bits down, in the direction of the shift arrow 272. In so doing, the contents of the shift register 200 at the eight selected bit locations 201, 209, 217, 225, 233, 241, 249, and 257 transfer the value to the immediately adjacent bit locations 202, 210, 218, 226, 234, 242, 250, and 258. After the contents of the 64-bit shift register 200 are shifted, the next 8-bit data element 290B is received into the data register 290, and thereby communicated to the eight selected bit locations 201, 209, 217, 225, 233, 241, 249, and 257. This shift 272 and load 271 process is repeated until the eight 8-bit data elements 290A, 290B, 290C, 290D, 290E, 290F, 290G, and 290H are loaded via the 8-bit register 290 into the 64-bit shift register 200. That is, for example, after seven shifts, the value from the second bit location 292 of the first 8-bit data element 290A will be located in the eighth bit location 208 of shift register 200, while the value from the second bit location 292 of the last 8-bit data element 290H will be located in the first bit location 201 of shift register 200. The values of the second bit location 292 of each of the intermediate 8-bit data elements 209B-209G will be located in the seventh 207 through second 202 register locations of the shift register 200. As illustrated in FIG. 2, the contents of the output register 290 are transferred to the eight selected bit locations 201, 209, 217, 225, 233, 241, 249, and 257 in a permuted form. This permuted form is the inverse of the permutation effected between the selected bit locations 108, 116, 124, 132, 140, 148, 156, and 164 of the 64-bit shift register 100 and the output register 190, illustrated in FIG. 1.
The DES permuted 64-bit transfer to and from an 8-bit data structure is fairly efficient in a system that uses an 8-bit architecture. However, an 8-bit architecture is no longer common in the art, having been supplanted by the common use of a 32-bit architecture. As illustrated in FIGS. 3 and 4, the conventional DES permuted 64-bit transfer is not particularly well suited to a system that uses a 32-bit architecture. As would be evident to one of ordinary skill in the art, because of the number of crossovers in the transfer paths 380 (480) of FIG. 3 (4) between the 64-bit shift register 300 (400) and the 32-bit data register 390 (490) the physical layout of the wiring between the shift register 300 (400) and the data register 390 (490) can be expected to be complex and area inefficient. Additionally, the structure presented in FIG. 3 (4) requires a 4-bit shift between unload (load) operations. To avoid the time required for a 4-bit shift, alternative architectures are used that employ non-standard devices and structures, requiring more time and effort to design and layout than conventional devices and structures. In like manner, in a software-based DES system, non-standard algorithms are typically required to move the contents of the shift register 300 to the data register 390, and the contents of the data register 490 to the shift register 400, because of the complex and somewhat non-algorithmic nature of the mapping.
It is an object of this invention to provide a DES permutation that is well suited for data transfers of 64-bit DES data structure to and from a 32-bit data structure. It is another object of this invention to provide a DES permutation that is area efficient for hardware implementations. It is another object of this invention to provide a DES permutation that is efficient in processing and transfer time. It is another object of this invention to provide a DES permutation that is computationally efficient for software implementations.
These objects and others are accomplished by providing a DES permutation that has minimal crossovers between the DES 64-bit structure and the 32-bit data structures, allows for efficient data transfer, and is easily encoded as a software algorithm. Every other bit location in the DES 64-bit data structure is mapped to a contiguous bit location in the 32-bit data structure, in a sequential order. The sequential mapping to contiguous bit locations minimizes potential crossovers that are area inefficient, and allows for encoding algorithms that effect the mapping by using incrementing operators only.